/*tree.h--二叉查找树接口头文件*/
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

//根据具体情况重新定义Item
#define SLEN 20		//树内容（字符串）的最大长度 
typedef struct item			//树的项的内容部分（项包括指针和内容）
{
	char petname[SLEN];
	char petkind[SLEN];
 }  Item;
 
 #define MAXITEMS 10	//树节点的最大数 
 
typedef struct trnode	//树的项（节点）,包括内容和两个子节点的指针 
{
	Item item;
	struct trnode* left;
	struct trnode* right;
} Trnode;

typedef struct tree		//树的整体,包括指向根节点的指针和树的项数
{
	Trnode* root;	//指向根节点的指针（树类似于链表，所以操纵树的整体和操纵链表的整体差不多，都是只需要首项的指针就行了。但不同于链表的是树是二叉查找，效率高了一倍）
	int size;		//树的项数 
} Tree;

/*函数原型*/

//操作：把树初始化为空
//前提条件:	ptree指向一个树
//后置条件: 树被初始化为空
void InitializeTree (Tree* ptree);

//操作: 确定树是否为空
//前提条件: ptree指向一个树
//后置条件: 如果树为空,函数返回true ,否则返回false
bool TreeIsEmpty (const Tree* ptree);

//操作: 确定树是否已满
//前提条件: ptree指向一个已初始化的树
//后置条件: 如果树已满,函数返回true,否则返回false
bool TreeIsFull (const Tree* ptree);

//操作: 确定树的项数
//前提条件: ptree指向一个已初始化的树 
//后置条件: 返回树的项数
int TreeItemCount (const Tree* ptree);

//操作: 在树中添加一个项
//前提条件: ptree指向一个树,pt是待添加项的地址 
//后置条件: 如果可以添加,则添加后返回true. 如果不能添加, 则树不变, 返回false
bool AddItem (const Item* pi, Tree* ptree);

//操作: 在树中查找一个项
//前提条件: ptree指向一个已初始化的树,pt是待查找的项的地址 
//后置条件: 在树中找到指定项后, 该函数返回true. 否则返回false
bool InTree (const Tree* ptree, const Item* pi);

//操作: 从树中删除一个项
//前提条件: pi是删除项的地址、ptree是已初始化的树 
//后置条件: 如果从树中成功删除一个项, 函数返回true, 否则返回false
bool DeleteItem (const Item* pi, Tree* ptree);

//操作: 把函数应用于树中的每一项
//前提条件: ptree是已初始化的树, pfun指向一个函数, 该函数接受一个Item类型的参数,无返回值
//后置条件: pfun指向的这个函数为树中的每一项执行一次
void Traverse (const Tree* ptree, void(*pfun)(Item item));

//操作: 删除树中的所有内容
//前提条件: ptree是已初始化的树
//后置条件: 树为空
void DeleteAll(Tree* ptree);

#endif
